package 面试经典150题.矩阵;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * @author tmh
 * @date 2024/6/18 22:07
 * @description
 */
public class T36有效的数独 {
    public boolean isValidSudoku(char[][] board) {
        //为每一行，每一列，每一个九成九的宫格都建立一个set集合，最后只需要判断set集合中是否包含重复的数就行
        //小方块和所属的每个9x9方格的关系是：idx=[i/3]*3+[j/3];
        Map<Integer, HashSet<Integer>> row = new HashMap<>();
        Map<Integer, HashSet<Integer>> col = new HashMap<>();
        Map<Integer, HashSet<Integer>> area = new HashMap<>();
        for (int i = 0; i < 9; i++) {
            //为每一行 每一列 每个面积进行初始化
            row.put(i, new HashSet<>());
            col.put(i, new HashSet<>());
            area.put(i, new HashSet<>());
        }
        //遍历矩阵
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if ('.' == c) {
                    continue;
                }
                //获得矩阵中小方块的值
                int num = c - '0';
                int idx = (i / 3) * 3 + (j / 3);
                //判断这个值在不在对应的行、对应的列以及对应9x9方格里面出现过，出现过就为false
                if (row.get(i).contains(num) || col.get(j).contains(num) || area.get(idx).contains(num)) {
                    return false;
                }
                //如果不在的话，就添加到对应的行 列 以及9x9方格里面
                row.get(i).add(num);
                col.get(j).add(num);
                area.get(idx).add(num);
            }
        }
        return true;
    }
}
